package com.zy.algorithm.v2;

import com.zy.algorithm.v2.bean.HeapSimpleNode;
import com.zy.utils.DataBuildUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HeapSortUtils {

    public static List<HeapSimpleNode> bucketSort(int size, int range) {
        int[] array = DataBuildUtils.getRandomSortArray(size, range);
        List<HeapSimpleNode> stepList = new ArrayList<>();
        List<Integer> sortedIndex = new ArrayList<>(); // 记录已排序坐标
        heapSort(stepList, sortedIndex, array);
        return stepList;
    }

    /**
     * 选择排序-堆排序
     *
     * @param array 待排序数组
     * @return 已排序数组
     */
    private static int[] heapSort(List<HeapSimpleNode> stepList, List<Integer> sortedIndex, int[] array) {


        //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(stepList, sortedIndex, array, i, array.length);  //调整堆
        }

        // 上述逻辑，建堆结束
        // 下面，开始排序逻辑

        for (int j = array.length - 1; j > 0; j--) {

            HeapSimpleNode heapSimpleNode = new HeapSimpleNode();
            heapSimpleNode.setStepStart(Arrays.copyOf(array, array.length)); //移动之前的数组
            heapSimpleNode.addOpIndex(j, 0);
            heapSimpleNode.setDes("最大堆");
            heapSimpleNode.setSortedIndexStart(sortedIndex);
            heapSimpleNode.setChange(true);
            heapSimpleNode.setChangeFIndex(0);
            heapSimpleNode.setChangeSIndex(j);


            // 元素交换,作用是去掉大顶堆
            // 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
            swap(array, 0, j);


            if (j == 1) {
                sortedIndex.add(0);
            }
            sortedIndex.add(j);
            heapSimpleNode.setStepEnd(Arrays.copyOf(array, array.length)); //移动之前的数组
            heapSimpleNode.setSortedIndexEnd(sortedIndex);


            stepList.add(heapSimpleNode);


            // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
            // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
            // 而这里，实质上是自上而下，自左向右进行调整的
            adjustHeap(stepList, sortedIndex, array, 0, j);
        }
        return array;
    }

    /**
     * 整个堆排序最关键的地方
     *
     * @param array  待组堆
     * @param i      起始结点
     * @param length 堆的长度
     */
    private static void adjustHeap(List<HeapSimpleNode> stepList, List<Integer> sortedIndex, int[] array, int i, int length) {
        // 先把当前元素取出来，因为当前元素可能要一直移动
        int temp = array[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树

            HeapSimpleNode heapSimpleNode = new HeapSimpleNode();
            heapSimpleNode.setStepEnd(Arrays.copyOf(array, array.length)); //移动之前的数组
            heapSimpleNode.setStepStart(Arrays.copyOf(array, array.length)); //移动之前的数组
            heapSimpleNode.addOpIndex(k, i);
            heapSimpleNode.setDes("最大堆");
            heapSimpleNode.setSortedIndexStart(sortedIndex);
            heapSimpleNode.setSortedIndexEnd(sortedIndex);
            stepList.add(heapSimpleNode);


            // 让k先指向子节点中最大的节点
            if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子树,并且右子树大于左子树
                k++;


                HeapSimpleNode heapSimpleNode1 = new HeapSimpleNode();
                heapSimpleNode1.setStepStart(Arrays.copyOf(array, array.length)); //移动之前的数组
                heapSimpleNode1.setStepEnd(Arrays.copyOf(array, array.length)); //移动之前的数组
                heapSimpleNode1.addOpIndex(k, i);
                heapSimpleNode1.setDes("最大堆");
                heapSimpleNode1.setSortedIndexStart(sortedIndex);
                heapSimpleNode1.setSortedIndexEnd(sortedIndex);
                stepList.add(heapSimpleNode1);
            }
            //如果发现结点(左右子结点)大于根结点，则进行值的交换
            if (array[k] > temp) {
                HeapSimpleNode heapSimpleNode2 = new HeapSimpleNode();
                heapSimpleNode2.setStepStart(Arrays.copyOf(array, array.length)); //移动之前的数组
                heapSimpleNode2.addOpIndex(k, i);
                heapSimpleNode2.setDes("最大堆");
                heapSimpleNode2.setSortedIndexStart(sortedIndex);
                heapSimpleNode2.setSortedIndexEnd(sortedIndex);
                heapSimpleNode2.setChange(true);
                heapSimpleNode2.setChangeFIndex(k);
                heapSimpleNode2.setChangeSIndex(i);


                swap(array, i, k);


                heapSimpleNode2.setStepEnd(Arrays.copyOf(array, array.length)); //移动之前的数组

                stepList.add(heapSimpleNode2);

                // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
                i = k;
            } else {  //不用交换，直接终止循环
                break;
            }
        }
    }

    /**
     * 交换元素
     *
     * @param arr
     * @param a   元素的下标
     * @param b   元素的下标
     */
    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}
